The -o flag for the key creation program is manditory. The extra credit applies only to the -c flag. I moved some paragraphs around in the write up below to make this point clearer.
Small typing error in XML format for private key pair. Instead of "dvalue" it was written "evalue". The current format below is the corrected one.
For this project, you are to write two programs that will perform Public-Key Encryption using the RSA Algorithm. The first program will create the public-key private-key pair. The second program will use a key to encrypt/decrypt an ASCII text message.The RSA alogorithm needs three related numbers to work. These number will be called e, d and n. The pair (e,n) compose the public-key, while the pair (d,n) compose the private key. To encrypt a value m into m' we preform the operation of:
m' = me mod n
To decrypt the value of m' back to m, we perform the operation of:
m = m'd mod n
Note that the value of m must be less than n in order for this to work.
Since we are encrypting/decrypting ASCII text messages and the largest
ASCII value is 127, the value of n must be at least 128.
The creation of the values of e, d and n start with the selection of two prime numbers p and q. The value of n is the result of p * q. Thus we need to make sure that the values p and q are large enough so that the resulting value of n is larger than any value we wish to encrypt.
n = p * q
To create e and d, we first must create a value φ which is:
φ = (p-1) * (q-1)
The value of e some arbitrary number that is less than n and relatively
prime to φ. There should be many numbers that fit this criteria
and any one is valid. A number x is relatively prime of y if they have
no divisor in common other than 1. This means the GCD (Greatest Common
Divisor) is 1. The GCD of two numbers can be computed via the
Euclidean Algorithm.
The value of d can be calculated once e has been determined. The value of d is the inverse of e modulo φ. Which means
(e * d) mod φ = 1
The calculation of both e and d is done via trial and error. You start
with a possible value and see if it is valid. If not, you change the
value and try again. This is done in a loop which exits when a valid
value is found. The code for calculation of e, d and n from the values
of p and q can be found at
http://www.profactor.at/~wstoec/rsa.html. Note that this code is
written in JavaScript and not commented. If you to use this code, you
must
The public key is to be store as:
<rsakey>
<evalue>value-of-e</evalue>
<nvalue>value-of-n</nvalue>
</rsakey>
The private key is to be stored as:
<rsakey>
<dvalue>value-of-d</dvalue>
<nvalue>value-of-n</nvalue>
</rsakey>
The program that creates the keys will need the values of p and q as input. Your program must allow these values can be given as command line arguments or allow the user to be prompted for these values while the program is being executed. Thus your program must parse the command line arguments are check if two integer values are given. If they are given, these are the values to be used for p and q. If they are not given, prompt the user to enter in these values. This prompting is to be done via a text-based interface. Once the values of p and q are supplied, your program must verify that they are different prime numbers. If they are not different prime numbers, an error is to be reported to the user and your program is to perform some "reasonable action". Your program must also verify that the prime numbers result in a value of n that is greater than 127. If the value of n is less than or equal to 127, an error is to be reported to the user and your program is to perform some "reasonable action".
The filenames that are used to contain the keys can be anything. Your program should use some default name if the user does not specify a name (such as key1, key2 or pubkey, prikey). The user is to be allowed specify the names via the command line flag of -o. Immediately following the flag two words should be given which will be used to hold the public key and the private key. If the user does not provide two words after the -o flag, an error is to be reported to the user and your program is to perform some "reasonable action".
The command line arguments can be given in any order as long as the two words for the key filenames immediately follow the -o flag if present.
For 5 points extra credit, your program can randomly generate two valid prime numbers for p and q. The user is to be able to inform your program to do this by either specifying the command line argument flag of -c or answering a prompt if the prime numbers are not given on the command line. To receive the extra credit, your program must allow both methods. The prime numbers generated must not always be the same pair of prime numbers (i.e. you can't just hardcode two prime numbers into your program).
The user can specify the file to be encrypted or decrypted on the command line with the flag of -f. The word immediately following the -f flag is the name of the file to be encrypted/decrypted. If the -f flag is not given, the program is to prompt the user for a filename. If the file does not exist or no name is given, an error is to be reported to the user and your program is to perform some "reasonable action". When encrypting a file, the file is expected to be an ASCII text file. When decrypting a file, the file is expected to contain one decimal integer value per line. If the file specified does not conform, an error is to be reported to the user and your program is to perform some "reasonable action".
The user can specify the key file to be used on the command line with the flag of -k. The word immediately following the -k flag is the name of the file that contains the key to be used. If the -k flag is not given, the program is to prompt the user for a filename. If the file does not exist or no name is given, an error is to be reported to the user and your program is to perform some "reasonable action". If the key file is not in the specified XML format, an error is to be reported to the user and your program is to perform some "reasonable action".
The user can specify the name of the resulting encrypted/decrypted file on the command line with the flag of -o. The word immediately following the -o flag is to be used as the filename to store the resulting file. If the -o flag is not give, the program is to prompt the user for a filename. If no name is given, an error is to be reported to the user and your program is to perform some "reasonable action".
One issue that may arise with this program is the size of the integer values as a result of the exponentiation required by the program. You may note that this program may create encrypted files that are not that difficult to decode. This is the result of only encoding one ASCII character at a time and allowing the use of small prime numbers for p and q.
Turnin your program electronically using the "turnin" command from your CS account as follows:
turnin -c cs340 -p mp1 [your project directory]
where the [your project directory] is the directory name under which you have
all your files related to this programming problem. The turnin command will
automatically compress the data under your directory, so there is no need to do
the compression by yourself.
Notice you can only invoke turnin command on the Linux machines in the lab or after logging into the server machine oscar.cs.uic.edu.
If you want to verify that your project was turned in, look in the turnin
directory for a file with your userid. For instance for this project, from your
CS account you would type:
turnin -c cs340 -v
Note that you can execute turnin as many times as you would like, up until the program deadline when turnin will be disabled for this project. Each time you execute turnin for a project, you overwrite all of what you had turned in previously for that project.It does not work in an incremental way.